package com.chao.sort;

import java.util.Arrays;

/**
 * @author : Rookie
 * @description :
 * @date : 2023/7/4
 */
public class QuickSort {

    public static void main(String[] args) {
        int []arr = new int[] {5,0,3,8,3,4,52,32,26,19,36};
        sort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));;
    }

    private static void sort(int []arr,int low,int high) {
        if (low > high) {
            return;
        }

        int pivotIndex = partition(arr, low, high);
        sort(arr,low,pivotIndex - 1);
        sort(arr,pivotIndex + 1,high);
    }

    private static int partition(int []arr,int low,int high) {
        int pivot = arr[low];
        int left = low + 1,right = high;

        while (left <= right) {
            // 移动左指针，直到找到大于基准值的元素
            while (left <= right && arr[left] <= pivot) {
                left++;
            }
            // 移动右指针，直到找到小于基准值的元素
            while (left <= right && arr[right] >= pivot) {
                right--;
            }

            if (left <= right) {
                // 将左指针和右指针对应的元素交换位置
                swap(arr, left, right);
            }
        }
        // 将基准值放到正确的位置
        swap(arr, low, right);
        System.out.println("left=" + left + "," + "right=" + right);
        return right;
    }

    private static void swap(int []arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
